package com.myapp.struts;

import java.util.Scanner;
import java.io.*;
import java.util.ArrayList;

public final class SearchEngine {
    private static String[] kataSambung = {"di","yang","ke","dari","dengan","atau","dan"};

    private String[] patterns;
    private String path;
    private Boolean isDFS;
    private Boolean isTitleOnly;
    private Boolean isKMP;

    public class Solution{
        public String keyword;
        public String title;
        public String extension;
        public String link;
        public String[] pattern;
    }

    public ArrayList<Solution> results;

    private static Boolean isFound(int[]array){
        for(int i = 0; i < array.length; i++){
            if(array[i] != -1)
                return true;
        }
        return false;
    }

    private static int indexOf(int k, int[]array){
        for(int i = 0; i < array.length; i++){
            if(array[i] == k)
                return array[i];
        }
        return -1;
    }

    public SearchEngine(String query, String path, Boolean isDFS, Boolean isTitleOnly, Boolean isKMP) throws FileNotFoundException, IOException{
        this.patterns = query.split(" ");
        this.path = path;
        this.isDFS = isDFS;
        this.isTitleOnly = isTitleOnly;
        this.isKMP = isKMP;
        results = new ArrayList();
        if(this.isDFS){
            searchDFS(this.path);
        }else{
            searchBFS(this.path);
        }
        giveSolutionBold();
    }

    public boolean isConjunction(String pattern) {
        boolean retval = false;
        for (int i=0; i<kataSambung.length; i++) {
            if (pattern.equals(kataSambung[i])) {
                retval = true;
            }
        }
        return retval;
    }

    public int[] borderCount(int m, String P) {
        int k, q;
        int[] output = new int[P.length()+1];
        output[0] = 0;
        output[1] = 0;
        q = 2;
        k = 0;
        for (q = 2; q < m; q++) {
            while ((k > 0) && (P.charAt(q-1)) != P.charAt(k)) {
                k = output[k];
            }
            if (P.charAt(q-1) == P.charAt(k)) {
                k++;
            }
            output[q] = k;
        }
        return output;
    }

    public int searchKMP (String text, String pattern) {
        int i, j;
        int m = pattern.length();
        int n = text.length();
        int[] b = new int[m+1];

        b = borderCount(m, pattern);
        j = 0;
        i = 1;
        boolean found = false;
        while (i<n+1 && !found) {
            while ((j>0) && (pattern.charAt(j)!=text.charAt(i-1))) {
                j = b[j];
            }
            if (pattern.charAt(j)==text.charAt(i-1)) {
                j++;
            }
            if (j == m) {
                found = true;
            } else {
                i++;
            }
        }
        if (found) {
            return i-m;
        } else {
            return -1;
        }
    }

    public int[] buildLast(String pattern) {
        int[] last = new int[128];
        for (int i = 0; i < last.length; i++) {
            last[i] = -1;
        }
        for (int i = 0; i < pattern.length(); i++) {
            last[pattern.charAt(i)] = i;
        }
        return last;
    }

    public int searchBM(String text, String pattern) {
        int last[] = buildLast(pattern);
        int n = text.length();
        int m = pattern.length();
        int i = m-1;

        if (i > n-1) {
            return -1;
        }
        int j = m-1;
        do {
            if (pattern.charAt(j) == text.charAt(i)) {
                if (j == 0) {
                    return i;
                } else {
                    i--; j--;
                }
            } else {
                int lo = last[text.charAt(i)];
                i = i + m - Math.min(j, 1+lo);
                j = m - 1;
            }
        } while (i <= n-1);
        return -1;
    }

    public int[] parseKMP(String text) {
        System.out.println();
        int[] result = new int[patterns.length];
        for (int i=0; i<patterns.length; i++) {
            if (!isConjunction(patterns[i])){
                System.out.println("Word: " + patterns[i] + " : " + searchKMP(text.toLowerCase(), patterns[i].toLowerCase()));
                result[i]= searchKMP(text.toLowerCase(), patterns[i].toLowerCase());
            }
        }
        System.out.println();
        return result;
    }

    public int[] parseBM(String text) {
        System.out.println();
        int[] result = new int[patterns.length];
        for (int i=0; i<patterns.length; i++) {
            if (!isConjunction(patterns[i])){
                System.out.println("Word: " + patterns[i] + ":" + searchBM(text.toLowerCase(), patterns[i].toLowerCase()));
                result[i] = searchBM(text.toLowerCase(), patterns[i].toLowerCase());
            }
        }
        System.out.println();
        return result;
    }

    public void compoundSolution(int[] result, String text, FileCustom dir){
        if(isFound(result)){
            Solution solution = new Solution();
            solution.title = dir.getName();
            solution.link = dir.getPath();
            solution.keyword = new String();
            solution.extension = dir.getExtension();
            solution.pattern = this.patterns;
            ArrayList<Integer> indices = new ArrayList();
            for(int i = 0; i <result.length; i++){
                if(result[i] != -1){
                    int begin = (result[i] - 30) < 0 ? 0 : (result[i] - 30);
                    int last = (result[i] + 30) > text.length() - 1 ? text.length() - 1 : (result[i] + 30);
                    if(!indices.contains(new Integer(begin)) && indices.contains(new Integer(last))){
                        for(int j = last; j <= begin; j--){
                            if(!indices.contains(new Integer(j))){
                                indices.add(0,j);
                            }
                        }
                    }else if(!(indices.contains(new Integer(begin)) && indices.contains(new Integer(last)))){
                        for(int j = begin; j <= last; j++){
                            if(!indices.contains(new Integer(j))){
                                indices.add(j);
                            }
                        }
                    }
                }
            }
            for(int i = 0; i < indices.size(); i++){
                if(i == 0){
                    if(indices.get(i).intValue() != 0)
                        solution.keyword =solution.keyword + "..." + text.charAt(indices.get(i));
                    else
                        solution.keyword =solution.keyword + text.charAt(indices.get(i));
                }else{
                    if(indices.get(i).intValue()-1 != indices.get(i-1).intValue())
                        solution.keyword =solution.keyword + "..." + text.charAt(indices.get(i));
                    else
                        solution.keyword =solution.keyword + text.charAt(indices.get(i));
                }
            }
            if(indices.get(indices.size()-1) != text.length()-1){
                solution.keyword = solution.keyword + "...";
            }
            results.add(solution);
        }
    }
    public void searchDFS(String path) throws FileNotFoundException, IOException{
        FileCustom dir = new FileCustom(path);
        if(dir.isFile() && (dir.getExtension().equals("doc") || dir.getExtension().equals("txt"))){
            String text = new String();
            text = dir.getName();
            if(!isTitleOnly){
                text = text + ". " + dir.readFile();
            }
            if(isKMP){
                int[] result = parseKMP(text);
                compoundSolution(result, text, dir);
            }else{
                int[] result = parseBM(text);
                compoundSolution(result, text, dir);
            }
        }else{
            String[] children = dir.list();
            if(children != null){
                for(int i = 0; i < children.length; i++){
                    System.out.println(dir.getPath()+"/"+children[i]);
                    searchDFS(dir.getPath()+"/"+children[i]);
                }
            }
        }
    }

    public void searchBFS(String path) throws FileNotFoundException, IOException{
        ArrayList<String> queue = new ArrayList();
        queue.add(path);
        while(!queue.isEmpty()){
            String _path = queue.remove(0);
            FileCustom dir = new FileCustom(_path);
            if(dir.isFile() && (dir.getExtension().equals("doc") || dir.getExtension().equals("txt"))){
                String text = new String();
                text = dir.getName();
                if(!isTitleOnly){
                    text = text + ". " + dir.readFile();
                }
                if(isKMP){
                    int[] result = parseKMP(text);
                    compoundSolution(result, text, dir);
                }else{
                    int[] result = parseBM(text);
                    compoundSolution(result, text, dir);
                }
            }else{
                String[] children = dir.list();
                if(children != null){
                    for(int i = 0; i < children.length;i++){
                        queue.add(dir.getPath()+"/"+children[i]);
                    }
                }
            }
        }
    }

    public void giveSolutionBold(){
        for(int i = 0; i < results.size(); i++){
            for(int j = 0; j < results.get(i).pattern.length; j++){
                String[] Title = results.get(i).title.split(" ");
                for(int k = 0; k < Title.length; k++){
                    if(Title[k].toLowerCase().contains(results.get(i).pattern[j].toLowerCase()))
                        Title[k] = "<b>"+Title[k]+"</b>";
                }
                results.get(i).title =  new String();
                for(int k = 0; k < Title.length; k++){
                    if(results.get(i).title.isEmpty()){
                        results.get(i).title = results.get(i).title + Title[k];
                    }else{
                        results.get(i).title = results.get(i).title + " " + Title[k];
                    }
                }

                String[] Keyword = results.get(i).keyword.split(" ");
                for(int k = 0; k < Keyword.length; k++){
                    if(Keyword[k].toLowerCase().contains(results.get(i).pattern[j].toLowerCase()))
                        Keyword[k] = "<b>"+Keyword[k]+"</b>";
                }
                results.get(i).keyword =  new String();
                for(int k = 0; k < Keyword.length; k++){
                    if(results.get(i).keyword.isEmpty()){
                        results.get(i).keyword = results.get(i).keyword + Keyword[k];
                    }else{
                        results.get(i).keyword = results.get(i).keyword + " " + Keyword[k];
                    }
                }
            }
        }
    }

    //public static void
    public static void main(String[] args) throws FileNotFoundException, IOException {
        // TODO code application logic here
        // parseKMP();
        Scanner consoleReader = new Scanner(System.in);
        System.out.print("Input Pattern: ");
        String pattern = consoleReader.nextLine();


        SearchEngine _search = new SearchEngine(pattern,"D:/wondersearch/WonderSearch",false,false,true);
        if(!_search.results.isEmpty()){
            for(int i = 0; i < _search.results.size();i++){
                System.out.println(_search.results.get(i).title+"."+_search.results.get(i).extension);
                System.out.println(_search.results.get(i).keyword);
            }
        }
    }

}